/**
 * @PackageName: PACKAGE_NAME
 * @ClassName: LeetCode1094
 * @Author: chen jinxu
 * @Date: 2022/3/31 22:06
 * @Description: //拼车
 * 车上最初有capacity个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）
 * 给定整数capacity和一个数组 trips , trip[i] = [numPassengersi, fromi, toi]
 * 表示第 i 次旅行有numPassengersi乘客，
 * 接他们和放他们的位置分别是fromi和toi。这些位置是从汽车的初始位置向东的公里数。
 * <p>
 * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回 false。
 * 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
 * 输出：false
 * 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
 * 输出：true
 *
 * 1 <= trips.length <= 1000
 * trips[i].length == 3
 * 1 <= numPassengersi<= 100
 * 0 <= fromi< toi<= 1000
 * 1 <= capacity <= 105
 */
public class LeetCode1094 {
    public static void main(String[] args) {
        int[][] trips = {{9, 0, 1}, {3, 3, 7}};
        boolean result = carPooling(trips, 4);
        System.out.println(result);
    }

    public static boolean carPooling(int[][] trips, int capacity) {
        int length = trips.length;
        int[] count = new int[1001];
        for (int i = 0; i < length; i++) {
            int numPassengers = trips[i][0];
            count[trips[i][1]] += numPassengers;
            count[trips[i][2]] -= numPassengers;
        }
        int sum = 0;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
            if (sum > capacity) {
                return false;
            }
        }
        return true;
    }

}
